#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef double db;

#define in read()
#define pii pair<int,int>
#define fi first
#define se second
#define FILE(x) freopen(x".in","r",stdin);\
	freopen(x".out","w",stdout);
#define pb push_back

int read(){
	int x = 0,sgn = 1;char ch = getchar();
	for(;!isdigit(ch);ch = getchar()) if(ch == '-') sgn = -1;
	for(;isdigit(ch);ch = getchar()) x = (x<<1)+(x<<3)+(ch^48);
	return x*sgn;
}

const int mod = 999911659;
const int P[] = {2,3,4679,35617};
const int N = 35620;

int a[5],g,n,G,cnt,d[N];
ll ans,fac[N],X,Y,ifac[N];

ll qp(ll x,int t,int md){ll res=1;for(;t;t>>=1,x=x*x%md) if(t&1) res = res * x % md;return res;}

ll C(int x,int y,int md){if(x < 0 || y < 0 || x < y) return 0;return fac[x] * ifac[y] % md * ifac[x - y] % md;}

void init_ca(int x){
	for(int i = (fac[0] = 1);i < x;i++) fac[i] = fac[i-1] * i % x; ifac[x - 1] = qp(fac[x-1],x-2,x);
	for(int i = x - 2;i >= 0;i--) ifac[i] = ifac[i+1] * (i + 1) % x;
}

ll luca(int x,int y,int md){
	if(x < md && y < md) return C(x,y,md);
	return luca(x / md,y / md,md) * C(x % md,y % md,md) % md;
}

void calc(int i){
	init_ca(P[i]); int md = P[i];
	for(int x = 1;x <= cnt;x++) a[i] = (a[i] + luca(n,d[x],md)) % md;
}

ll gcd(ll x,ll y){return !y ? x : gcd(y,x%y);}

ll lcm(ll x,ll y){return x / gcd(x,y) * y;}

void exgcd(ll a,ll b){
	if(!b){G = a; X = 1;Y = 0;return;}
	exgcd(b,a%b); ll tx = X; X = Y; Y = tx - a / b * Y;
}

bool merge(ll x1,ll m1,ll x2,ll m2,ll &x3,ll &m3){
	x1 %= m1;x2 %= m2;
	m3 = lcm(m1,m2); ll t = ((x2 - x1) % m2 + m2) % m2;
	exgcd(m1,m2);
	if(t % G != 0) return false;
	t /= G; X = X * t % m2; X += m2; X %= m2;
	x3 = X * m1 % m3 + x1; x3 %= m3; x3 = (x3 + m3) % m3;
	return true;
}

signed main (){
#ifndef ONLINE_JUDGE
	freopen("1.in","r",stdin);
#endif
	n = in,g = in;
	if(g % mod == 0) return puts("0"),0;
	for(int i = 1;i * i <= n;i++){
		if(n % i == 0){
			d[++cnt] = n / i;
			if(i != n / i) d[++cnt] = i;
		}
	}
	for(int i = 0;i < 4;i++) calc(i);
	ll M = 1,x = 0;
	for(int i = 0;i < 4;i++) if(!merge(x,M,a[i],(ll)P[i],x,M)) return puts("-1"),0;
	ll ans = qp(g,x,mod) % mod;
	printf("%lld\n",ans);
	return 0;
}
